Statement#

You need to find the minimum number of refueling stops that a car needs to make to cover a distance, target. For simplicity, assume that the car has to travel from west to east in a straight line. There are various fuel stations on the way, that are represented as a 2-D array of stations, i.e., stations[i] =[di,fi]= [d_i, f_i], where did_i is the distance in miles of the ithi^{th} gas station from the starting position, and fif_i is the amount of fuel in liters that it stores. Initially, the car starts with k liters of fuel. The car consumes one liter of fuel for every mile traveled. Upon reaching a gas station, the car can stop and refuel using all the petrol stored at the station. In case it cannot reach the target, the program simply returns 1-1.

Note: If the car reaches a station with 00 fuel left, it can refuel from that station, and all the fuel from that station can be transferred to the car. If the car reaches the target with 00 fuel left, it is still considered to have arrived.

For example:

  • target: 1515
  • start fuel: 22
  • stations: [[1,2],[2,8],[4,10],[6,7],[7,2],[8,1]][[1, 2], [2, 8], [4, 10], [6, 7], [7, 2], [8, 1]]

If we want to reach the target of 15 miles, we have to refuel from a minimum of 22 stations to reach the target. First, we will refuel our car with 88 liters from the second station and then refuel 1010 liters from the third station.

Constraints:

  • 11 \leq target, k 109\leq 10^9
  • 00 \leq stations.length 900\leq 900
  • 1di<di+1<1 \leq d_{i} < d_{i+1}< target
  • 1fi<1091 \leq f_{i} < 10^9

Examples#

No.

Target

Start Fuel

Stations

Refueling Stops

1

15

2

[[1, 2], [2, 8], [4, 10], [6, 7], [7, 2], [8, 1]]

2

2

120

10

[[10, 60], [20, 25], [30, 30], [60, 40]]

3

Try it yourself#

Implement your solution in the following coding playground:

Python
usercode > main.py
Input #1
Input #2
Input #3
Minimum Number of Refueling Stops

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the 0/1 Knapsack dynamic programming pattern.

Naive approach#

A naive approach is to find all the combinations of the first refueling stop, then the second refueling stop, and so on, until all the combinations of nn refueling stops are found. Once we have all these combinations, we will select the combination that will help us reach the target with the minimum number of refueling stops in between. To do this, we need a recursive solution to make all the possible combinations. In other words, we divide the problem into subproblems and, for each fueling station, we decide whether to include it or not in the count of refueling stations.

Now, we will see the intuition behind recursive calls. Suppose min_refuel_stops_helper(index, used) is the farthest point the car can reach by refueling at exactly the used number of refueling stations among the first index number of refueling stations. Then the recursive call will be like this:

min_refuel_stops_helper(index, used) = max(min_refuel_stops_helper(index-1, used-1) + fuel at station index , min_refuel_stops_helper(index-1, used))

For example:

  • target: 100100
  • start fuel: 1010
  • stations: [[10,60],[20,25],[30,30]][[10, 60], [20, 25], [30, 30]]

With a start fuel of 1010 liters, we will check the fuel stations we can reach. As a result, we can only travel to fuel station 1 with 1010 liters of fuel. In simpler words, we can only cover a distance of 1010 miles.

After collecting all the available fuel from fuel station 1, we can cover a total distance of 7070 miles as per the following calculation:

1010 (starting fuel) + 6060 (fuel from station 1) = 7070.

Next, we can travel to both stations 2 and 3 because the fuel required for station 2 is 2020 liters and station 3 is 3030 liters. If we choose station 2, we will end up with a total distance of 9595 miles, but this will still be less than our target distance of 100100 miles, so we will need to travel to station 3 as well and collect the available fuel, making a total distance of 125125 miles which is greater than our target. This way, to reach the target, we need to travel to 3 fueling stations.

But if we directly travel to fuel station 3 after fuel station 1, then we will end up with a total travel distance of 100100 miles, which is equal to our target of 100100 miles. This way, we only need to travel to 2 fueling stations.

So we will choose the second combination because it has the minimum number of fueling stations required to reach the target.

Let’s implement the algorithm as discussed above:

Minimum Number of Refueling Stops using recursion

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of this naive approach is n×2nn\times2^n, where nn is the number of available stations.

Space complexity#

The space complexity of this naive approach is O(n)O(n).

Optimized solution using dynamic programming#

Now, let’s improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in an array. In the naive approach above, we do not store the maximum distance value for each combination of refueling stops for later use. Therefore, we end up computing them repeatedly.

In the memoization-based approach, we store the computed values in a lookup table when we encounter a combination of refueling stops for the first time. Prior to making a recursive call to the function, we check if the desired refueling combination result exists in the lookup table. If it does, we simply return the previously stored value. Otherwise, a recursive call is made to the function to compute the result.

Let’s implement the algorithm as discussed above:

Minimum Number of Refueling Stops using memoization

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity of the algorithm above is O(n2)O(n^2), where nn is the number of available stations.

Space complexity#

We are using a 2-D array to store the maximum distance. So, the space complexity is O(n2)O(n^2).

Bottom-up solution#

The bottom-up solution, also known as the tabulation method, is an iterative method of solving dynamic programming problems. We start off by constructing a 2-D array of size (n+1)×(n+1)(n+1) \times (n+1) for tabulation, where nn is the total number of stations. We call this 2-D array dp and initialize it with zeroes. Now, we start filling the array in a bottom-up manner. Each entry in this array tells us the distance covered so far to reach the specific station.

Here is how we implement this algorithm:

  • Initialize lookup table of size (n+1)×(n+1)(n+1) \times (n+1).

  • If we do not use any fuel stop, then the max distance will be the start fuel. Therefore, we fill up the first column of the table with the start fuel.

  • For each station ii:

    • For each fueling stop j=1j = 1 to j=ij = i
      • If the car can reach the next station, then update the lookup table as follows: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + station i's fuel).
      • Otherwise, the max distance will be the max reachable distance of the previous station; update the lookup table as follows: dp[i][j] = dp[i - 1][j].
  • After visiting all the stations, find the minimum j, which has distance >= target. This will be our minimum number of refueling stops to reach the target.

Let’s look at the following illustration to get a better understanding of the solution:

Created with Fabric.js 3.6.6 stations [10, 60] [20, 25] [30, 30] [60, 40] Start fuel 10 Target 120

1 of 14

Created with Fabric.js 3.6.6 stations [10, 60] [20, 25] [30, 30] [60, 40] Start fuel 10 Target 120 0 1 2 3 4 0 0 0 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 3 0 0 0 0 0 4 0 0 0 0 0 Create a matrix of size (n+1)*(n+1) and initialize it with zero.

2 of 14

Created with Fabric.js 3.6.6 stations [10, 60] [20, 25] [30, 30] [60, 40] Start fuel 10 Target 120 0 1 2 3 4 0 10 0 0 0 0 1 10 0 0 0 0 2 10 0 0 0 0 3 10 0 0 0 0 4 10 0 0 0 0 If we do not use any fuel stop, then the max distancewill be the start fuel. Therefore, we fill up the firstcolumn of the table with the Start fuel = 10. The remainingfirst row will contain all 0s, since we are stopping at the firstfuel stop and aern't using it to go further.

3 of 14

Created with Fabric.js 3.6.6 Start fuel 10 Target 120 i 1 j 1 0 1 2 3 4 0 10 0 0 0 0 1 10 70 0 0 0 2 10 0 0 0 0 3 10 0 0 0 0 4 10 0 0 0 0 stations [10, 60] [20, 25] [30, 30] [60, 40] Condition dp[i - 1][j - 1] >= stations[i - 1][0] : TRUERefuel at current stationdp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + stations[i - 1][1])dp[1][1] = max(dp[1 - 1][1], dp[1 - 1][1 - 1] + stations[1 - 1][1])dp[1][1] = max(0, 10 + 60) = 70

4 of 14

Created with Fabric.js 3.6.6 Start fuel 10 Target 120 i 2 j 1 0 1 2 3 4 0 10 0 0 0 0 1 10 70 0 0 0 2 10 70 0 0 0 3 10 0 0 0 0 4 10 0 0 0 0 stations [10, 60] [20, 25] [30, 30] [60, 40] Condition dp[i - 1][j - 1] >= stations[i - 1][0] : FALSEDo not refuel at current stationdp[i][j] = dp[i - 1][j]dp[2][1] = dp[2 - 1][1]dp[2][1] = dp[1][1] = 70

5 of 14

Created with Fabric.js 3.6.6 Start fuel 10 Target 120 i 2 j 2 0 1 2 3 4 0 10 0 0 0 0 1 10 70 0 0 0 2 10 70 95 0 0 3 10 0 0 0 0 4 10 0 0 0 0 stations [10, 60] [20, 25] [30, 30] [60, 40] Condition dp[i - 1][j - 1] >= stations[i - 1][0] : TRUERefuel at current stationdp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + stations[i - 1][1])dp[2][2] = max(dp[2 - 1][2], dp[2 - 1][2 - 1] + stations[2 - 1][1])dp[2][2] = max(0, 70 + 25) = 95

6 of 14

Created with Fabric.js 3.6.6 Start fuel 10 Target 120 i 3 j 1 0 1 2 3 4 0 10 0 0 0 0 1 10 70 0 0 0 2 10 70 95 0 0 3 10 70 0 0 0 4 10 0 0 0 0 stations [10, 60] [20, 25] [30, 30] [60, 40] Condition dp[i - 1][j - 1] >= stations[i - 1][0] : FALSEDo not refuel at current stationdp[i][j] = dp[i - 1][j]dp[3][1] = dp[3 - 1][1]dp[3][1] = dp[2][1] = 70

7 of 14

Created with Fabric.js 3.6.6 Start fuel 10 Target 120 i 3 j 3 stations [10, 60] [20, 25] [30, 30] [60, 40] 0 1 2 3 4 0 10 0 0 0 0 1 10 70 0 0 0 2 10 70 95 0 0 3 10 70 100 0 0 4 10 0 0 0 0 Condition dp[i - 1][j - 1] >= stations[i - 1][0] : TRUERefuel at current stationdp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + stations[i - 1][1])dp[3][2] = max(dp[3 - 1][2], dp[3 - 1][2 - 1] + stations[3 - 1][1])dp[3][2] = max(95, 70 + 30) = 100

8 of 14

Created with Fabric.js 3.6.6 Start fuel 10 Target 120 i 3 j 3 0 1 2 3 4 0 10 0 0 0 0 1 10 70 0 0 0 2 10 70 95 0 0 3 10 70 100 125 0 4 10 0 0 0 0 stations [10, 60] [20, 25] [30, 30] [60, 40] Condition dp[i - 1][j - 1] >= stations[i - 1][0] : TRUERefuel at current stationdp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + stations[i - 1][1])dp[3][3] = max(dp[3 - 1][3], dp[3 - 1][3 - 1] + stations[3 - 1][1])dp[3][3] = max(0, 95 + 30) = 125

9 of 14

Created with Fabric.js 3.6.6 Start fuel 10 Target 120 i 4 j 1 0 1 2 3 4 0 10 0 0 0 0 1 10 70 0 0 0 2 10 70 95 0 0 3 10 70 100 125 0 4 10 70 0 0 0 stations [10, 60] [20, 25] [30, 30] [60, 40] Condition dp[i - 1][j - 1] >= stations[i - 1][0] : FALSEDo not refuel at current stationdp[i][j] = dp[i - 1][j]dp[4][1] = dp[4 - 1][1]dp[4][1] = dp[3][1] = 70

10 of 14

Created with Fabric.js 3.6.6 Start fuel 10 Target 120 i 4 j 2 0 1 2 3 4 0 10 0 0 0 0 1 10 70 0 0 0 2 10 70 95 0 0 3 10 70 100 125 0 4 10 70 110 0 0 stations [10, 60] [20, 25] [30, 30] [60, 40] Condition dp[i - 1][j - 1] >= stations[i - 1][0] : TRUERefuel at current stationdp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + stations[i - 1][1])dp[4][2] = max(dp[4 - 1][2], dp[4 - 1][2 - 1] + stations[4 - 1][1])dp[4][2] = max(100, 70 + 40) = 110

11 of 14

Created with Fabric.js 3.6.6 Start fuel 10 Target 120 i 4 j 3 0 1 2 3 4 0 10 0 0 0 0 1 10 70 0 0 0 2 10 70 95 0 0 3 10 70 100 125 0 4 10 70 110 140 0 stations [10, 60] [20, 25] [30, 30] [60, 40] Condition dp[i - 1][j - 1] >= stations[i - 1][0] : TRUERefuel at current stationdp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + stations[i - 1][1])dp[4][3] = max(dp[4 - 1][3], dp[4 - 1][3 - 1] + stations[4 - 1][1])dp[4][3] = max(125, 100 + 40) = 140

12 of 14

Created with Fabric.js 3.6.6 Start fuel 10 Target 120 i 4 j 4 0 1 2 3 4 0 10 0 0 0 0 1 10 70 0 0 0 2 10 70 95 0 0 3 10 70 100 125 0 4 10 70 110 140 165 stations [10, 60] [20, 25] [30, 30] [60, 40] Condition dp[i - 1][j - 1] >= stations[i - 1][0] : TRUERefuel at current stationdp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + stations[i - 1][1])dp[4][4] = max(dp[4 - 1][4], dp[4 - 1][4 - 1] + stations[4 - 1][1])dp[4][4] = max(0, 125 + 40) = 165

13 of 14

Created with Fabric.js 3.6.6 Start fuel 10 Target 120 0 1 2 3 4 0 10 0 0 0 0 1 10 70 0 0 0 2 10 70 95 0 0 3 10 70 100 125 0 4 10 70 110 140 165 stations [10, 60] [20, 25] [30, 30] [60, 40] Return the minimum j, where dp[n][i] >= Target, that will be our minimum number of refueling stops to reach the target, that is 3.

14 of 14

Let’s implement the algorithm as discussed above:

Minimum Number of Refueling Stops using tabulation

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity of the algorithm above is O(n2)O(n^2), where nn is the number of available stations.

Space complexity#

We are using a 2-D array of elements to store the maximum distance. So, the space complexity is O(n2)O(n^2).

Can we do better?#

When filling up the distance values for each station, we only require the station above it in the matrix and not any previous station’s result. This means we only need to retain the data of the last row. So, we can use a 1-D array instead of a 2-D array, which will further reduce the space complexity from O(n2)O(n^2) to O(n)O(n).

Partition Array Into Two Arrays to Minimize Sum Difference

Equal Sum Subarrays